1. Field of Invention
This invention relates to a memory device for high performance real-time graphics systems for displaying flat-shaded polygons, typically used for, but not limited to, the display of 3D graphics. More specifically, this invention relates to a Z-Buffer, so named because most three dimensional systems use coordinate axes oriented so that the Z axis points straight ahead. However, because some systems do not have the Z axis pointing straight ahead, the term Depth Buffer is a more general description. Nonetheless, for the purposes of this application the terms Depth Buffer and Z-Buffer will mean the same thing.
2. Discussion of Prior Art
When displaying polygons representing 3D surfaces it is common that some polygons obscure other polygons, either partially or completely. In order for the result to be realistic it is necessary that the obscured (or hidden) surfaces not be drawn.
A simple method is to sort the polygons according to their distance to the viewer. The polygons that are the farthest from the viewer are drawn into the frame buffer first. The polygons that are closest to the viewer are drawn last, thereby having the opportunity of overwriting any polygons (either whole or in part) that are farther away.
There are two problems with simple polygon sorting. One is that it is computationally intensive for large numbers of polygons. The other problem is that polygons that intersect are not handled properly. The polygon that is drawn last will dominate.
A method for dealing with this second problem is taught in U.S. Pat. No. 3,889,107 SYSTEM OF POLYGON SORTING BY DISSECTION, issued Jun. 10, 1975 to Sutherland. In this method any polygon which straddles a plane of subdivision is dissected into two parts which are thereafter treated separately.
An early reference to the use of Z-Buffers can be found in the textbook by Newman & Sproull, "Principles of Interactive computer Graphics (Second Edition)" McGraw-Hill, 1979., pp. 369-371.
"Of all image-space algorithms, the depth buffer algorithm is the simplest. For each pixel on the display screen, we keep a record of the depth of the object within the pixel that lies closest to the observer. In addition to the depth, we also record the intensity that should be displayed to show the object. In this respect, the depth-buffer is an extension of a frame buffer.
The depth-buffer algorithm given below requires two arrays, intensity and depth, each of which is indexed by pixel coordinates (x,y).
Depth Buffer Algorithm
1. For all pixels on the screen, set depthx,y! to 1.0 and intensityx,y! to a background value. PA1 2. For each polygon in the scene, find all pixels (x,y) that lie within the boundaries of the polygon when projected onto the screen. For each of these pixels: PA1 "The main drawback to reading every Pixel Hit out of the MCCAM Z-buffer 11000, 23000, or 39000 is similar to the above described drawback to the one-by-one writing of new z-values into the MCCAM Z-buffer 11000, 23000, or 39000. Reading (or writing) all the Pixel Hits can consume a major fraction of the memory access bandwidth of the MCCAM Z-buffer 11000, 23000, or 39000." See Column 28, lines 60-67.
a. Calculate the depth z of the polygon at (x,y). PA2 b. If z&lt;depthx,y!, this polygon is closer to the observer than others already recorded for this pixel. In this case, set depthx,y! to z and intensityx,y! to a value corresponding to the polygon's shading. If instead z&gt;depthx,y!, the polygon already recorded at (x,y) lies closer to the observer than does this new polygon, and no action is taken."
Since then, there have been numerous patents concerning Z-Buffers. They range from purely software methods to methods incorporating specialized hardware. What almost all of them have in common is that they use conventional computer memories.
An example of a combination software and hardware method is shown in U.S. Pat. No. 5,081,698 METHOD AND APPARATUS FOR GRAPHICS DISPLAY DATA MANIPULATION, issued Jan. 14, 1992 to Kohn. This patent teaches that a portion of a single chip processor is physically dedicated to graphics oriented processing, and a set of graphics oriented instructions are provided that substantially accelerate the graphics pipeline throughput.
A method incorporating specialized hardware is taught in U.S. Pat. No. 4,924,415 APPARATUS FOR MODIFYING DATA STORED IN A RANDOM ACCESS MEMORY, issued May 8, 1990 to Winser. This method uses standard VRAMs to implement a pipelined Z-Buffer for Hidden Surface Removal (HSR). The VRAM serial access port is used synchronously with the writing operations to the main array to extract the current z-values from the main z-RAM array rather than for repetitive display refresh purposes.
A method that does not use conventional computer memories is shown in U.S. Pat. No. 5,544,306 FLEXIBLE DRAM ACCESS IN A FRAME BUFFER MEMORY AND SYSTEM, issued Aug. 6, 1996 to Deering et al. This is a Z-buffer IC that performs the Z compare internally instead of in software. The Frame Buffer Memory (FBRAM) uses four DRAMs of conventional design along with a high speed SRAM cache and a pixel ALU. Although the FBRAM does not use conventional memories as such, the internal DRAMs are of conventional design.
Another method that does not use conventional computer memories is shown in U.S. Pat. No. 5,596,686 METHOD AND APPARATUS FOR SIMULTANEOUS PARALLEL QUERY GRAPHICS RENDERING Z-COORDINATE BUFFER issued Jan. 21, 1997 to Duluk. Duluk uses a specialized IC called a "Magnitude Comparison Content Addressable Memory" (MCCAM) which determines whether or not a polygon is obscured by previous polygons before handing it over to a rendering engine. If the polygon is obscured by previous polygons, no further action is required. If the polygon is not obscured by previous polygons, the rendering engine renders it and uses a second (standard) Z-Buffer along with a frame buffer of standard design. This is shown in Duluk FIG. 14. The MCCAM does the comparison on all polygon points simultaneously. However, getting points into and out of the MCCAM can be slow.
The operation of a Row Addressable Graphics Memory With Flash Fill is taught in U.S. Pat. NO. 5,422,998 VIDEO MEMORY WITH FLASH FILL issued Jun. 6, 1995 and U.S. Pat. NO. 5,553,229 ROW ADDRESSABLE GRAPHICS MEMORY WITH FLASH FILL issued Sep. 3, 1996, both issued to the present applicant. A Row Addressable Graphics Memory With Flash Fill is a single-chip semiconductor memory device optimized for high performance flat-shaded polygon video systems and consists of a RAM with flash fill circuitry whereby the Start and End addresses are specified for a given row; the data within this range are read, modified, and written back to the memory in parallel thereby requiring a maximum of three memory cycles to fill a line segment independent of the length of the line. The data are modified according to a function between a color register and the data already present in the memory array, the functions being: AND, OR, EXCLUSIVE OR, or REPLACE.
With the exception of the Duluk patent, prior art Z-Buffers use conventional computer memories which limit the number of Z values that can be accessed in each memory cycle. For example, even with a 64-bit data path, a system having 16-bit Z values can only access four Z values per memory access. Even in the Duluk patent, the amount of data that can be accessed before sending it to the second (standard) Z-Buffer is limited by the size of the data bus.